package leetcode.tree;

import leetcode.tree.common.TreeNode;

import java.util.Stack;

/**
 * @author mazouri
 * @create 2021-08-22 17:16
 */
public class _230_kthSmallest {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            if (--k == 0) return cur.val;

            cur = cur.right;
        }

        return -1;
    }
}
